#include <string>
#include <vector>
using namespace std;
/*
dp[i][j]: word1[:i]和word2[:j]相同最少需要的编辑次数
如果 word[i] == word[j] 则
    dp[i][j] = dp[i-1][j-1]
如果 word[i] != word[j] 则
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    dp[i-1][j]: 添加一个元素
    dp[i][j-1]: 删除一个元素
    dp[i-1][j-1]: 替换一个元素

*/
int minDistance(string word1, string word2) {
  vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
  for (int i = 0; i <= word1.size(); ++i) {
    dp[i][0] = i;
  }
  for (int j = 0; j <= word2.size(); ++j) {
    dp[0][j] = j;
  }
  for (int i = 1; i <= word1.size(); ++i) {
    for (int j = 1; j <= word2.size(); ++j) {
      if (word1[i - 1] == word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[word1.size()][word2.size()];
}